package Leetcode.树;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @Author: kirito
 * @Description:
 * 前序：根左右
 * 中序：左根右
 * 感觉用草稿纸画图比较好画出来。。。
 * @Date: 2024/2/29 12:51
 * @Version: 1.0
 */

public class 从前序与中序遍历序列构造二叉树 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //记录每个节点值对应在中序遍历种的索引
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        //root为先序的第一个节点 0开始
        return recur(preorder, map, 0, 0, inorder.length - 1);
    }

    private TreeNode recur(int[] preorder, HashMap<Integer, Integer> map, int root, int left, int right) {
        if (left > right) {
            return null;
        }
        // 建立根节点
        TreeNode node = new TreeNode(preorder[root]);
        // 获取根节点在中序中的索引，i-1就是right左子树的右边界 i+1就是右子树的左边界
        int i = map.get(preorder[root]);
        //左子树的根是当前节点root+1，对应的是先序中的索引
        node.left = recur(preorder, map, root + 1, left, i - 1);
        //i - left + root + 1含义为 根节点索引 + 左子树长度 + 1
        node.right = recur(preorder, map, root + i - left + 1, i + 1, right);
        return node;
    }

    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}
